#ifndef SORTING_H
#define SORTING_H

#include<iostream>
#include<vector>
#include<functional>
#include<algorithm>
#include<ctime>
using namespace std;

//插入排序，用于小数组的排序。
template <typename Comparable>
void insertionSort1( vector<Comparable> & a, int left, int right )
{
    for( int p = left + 1; p <= right; ++p )
    {
        Comparable tmp = std::move( a[ p ] );
        int j;

        for( j = p; j > left && tmp < a[ j - 1 ]; --j )
            a[ j ] = std::move( a[ j - 1 ] );
        a[ j ] = std::move( tmp );
    }
}


//利用随机主元选取法定义的快速排序函数。
template <typename Comparable>
void quicksort1( vector<Comparable> & a, int left, int right )
{
    if( left + 10 <= right )
    {
        srand(unsigned(time(0)));  //调用随机数前重置随机种子
        int r = (rand() % (right - left + 1)) + left;  //随机生成主元的位置
        Comparable pivot = a[r];
        std::swap(a[left],a[r]);  //交换到区间端点位置

        //区间内元素的遍历和分割
        int i = left, j = right + 1;
        for( ; ; )
        {
            while( a[ ++i ] < pivot ) { }
            while( pivot < a[ --j ] ) { }
            if( i < j )
                std::swap(a[i],a[j]);
            else    
                break;
        }

        std::swap(a[left],a[j]);  //主元回到中间位置。
        //对左右两边的小区间进行递归。
        quicksort1( a, left, j - 1 );     
        quicksort1( a, j + 1, right );    
    }
    else  
        //对小数组进行插入排序。
        insertionSort1( a, left, right );
}

//供外部调用的借口函数。
template <typename Comparable>
void quicksort1( vector<Comparable> & a )
{
    quicksort1( a, 0, a.size( ) - 1 );
}


//利用三区间分割法定义的快速排序函数。
template <typename Comparable>
void quicksort2( vector<Comparable> & a, int left, int right )
{
    if( left + 10 <= right )
    {
        srand(unsigned(time(0)));  //调用随机数前重置随机种子
        int r = (rand() % (right - left + 1)) + left;  //随机生成主元的位置
        Comparable pivot = a[r];
        std::swap(a[left],a[r]);  //交换到区间端点位置

        //区间内元素的遍历和分割
        //主元最开始在区间最左侧，即left位置。
        //随着比较与交换操作的过程，出现第一个小于主元的元素时，
        //主元会被交换到等于主元部分区间的第一个位置。
        //lt存储等于主元部分区间的最左端位置。
        //rt存储等于主元部分区间的最右端位置。
        int i = left + 1, lt = left, rt = right;
        while( i <= rt ){
            if( a[i] < pivot )
            {
                //移到lt的位置，且区间端点lt加1。
                std::swap( a[lt], a[i] );
                lt++;  i++;
            }
            else if( a[i] > pivot )
            {
                //移到rt的位置，且区间端点rt减1。
                //由于从rt处换过来的元素未确定大小，所以遍历的
                //下标i不能加1，要在原来位置继续判断。
                std::swap( a[rt], a[i]);
                rt--;  
            }
            else
                i++;
        }

        //对左右两边的小区间进行递归。
        quicksort2( a, left, lt-1 );
        quicksort2( a, rt+1, right );
    }
    else  
        //对小数组进行插入排序。
        insertionSort1( a, left, right );
}

//供外部调用的接口函数。
template <typename Comparable>
void quicksort2( vector<Comparable> & a )
{
    quicksort2( a, 0, a.size( ) - 1 );
}


#endif